#include<iostream>
#include<vector>
using namespace std;
/*
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
解题思路：
与上一道最少删除元素的次数题目类似，该题加了添加元素和修改元素的操作
假设dp数组的dp[i][j]表示的是word1以下标i-1结尾的字符和word2以下标j-1为结尾的字符最少操作dp[i][j]次数变得相同
若word[i]==word[j]
dp[i][j] = dp[i-1][j-1]
若不等于的话,则需要进行操作
举例假设word1 = abc
word2 = ab
且b！=c;
则考虑删除word1中的c或者word2中的b（添加操作等同于逆向的删除操作,如word1中添加b，word2中添加c，操作次数与删除相同）
或者考虑修改操作，将word1中的c改为b或者将word2中的b改为c(该最小操作次数是i-1和j-1下标之前的最小操作次数加1)，求三种情况的最小者
dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1],dp[i-1][j-1]+1))
如何进行初始化
dp[i][0]表示word1以下标为i-1结尾的元素与word2中下标为-1结尾的元素变为相同的最少操作次数(进行i次删除操作)dp[i][0] = i;
dp[0][j]表示word2以下标为j-1结尾的元素与word1中下标为-1结尾的元素变为相同的最少操作次数（进行j次删除操作）dp[0][j] = j;
*/
int dp(string word1,string word2)
{
    //创建dp数组
    vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
    //初始化
    for(int i=0;i<=word1.size();i++)
        dp[i][0] = i;
    for(int i=0;i<=word2.size();i++)
        dp[0][i] = i;
    //遍历
    for(int i=1;i<=word1.size();i++)
    {
        for(int j=1;j<=word2.size();j++)
        {
            if(word1[i-1]==word2[j-1])
                dp[i][j]=dp[i-1][j-1];
            else
                dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));
        }
    }
    return dp[word1.size()][word2.size()];
}
int main()
{
    cout<<"enter word1:"<<endl;
    string word1;
    cin>>word1;
    cout<<"enter word2:"<<endl;
    string word2;
    cin>>word2;
    cout<<dp(word1,word2);
    return 0;
}